package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC327 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 本题目的方法二至方法五均用到了较高级的数据结构，读者一般只需掌握方法一即可，感兴趣的读者可以学习其他四种解法。
     * 官方题解就是高大上！
     * 图解思路好的解法：https://leetcode-cn.com/problems/count-of-range-sum/solution/fen-zhi-si-xiang-ying-yong-gui-bing-pai-xu-zuo-yi-/
     * @return:
     */
    class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            long s = 0;
            long[] sum = new long[nums.length + 1];
            for (int i = 0; i < nums.length; ++i) {
                s += nums[i];
                sum[i + 1] = s;
            }
            return countRangeSumRecursive(sum, lower, upper, 0, sum.length - 1);
        }

        public int countRangeSumRecursive(long[] sum, int lower, int upper, int left, int right) {
            if (left == right) {
                return 0;
            } else {
                int mid = (left + right) / 2;
                int n1 = countRangeSumRecursive(sum, lower, upper, left, mid);
                int n2 = countRangeSumRecursive(sum, lower, upper, mid + 1, right);
                int ret = n1 + n2;

                // 首先统计下标对的数量
                int i = left;
                int l = mid + 1;
                int r = mid + 1;
                while (i <= mid) {
                    while (l <= right && sum[l] - sum[i] < lower) {
                        l++;
                    }
                    while (r <= right && sum[r] - sum[i] <= upper) {
                        r++;
                    }
                    ret += r - l;
                    i++;
                }

                // 随后合并两个排序数组
                long[] sorted = new long[right - left + 1];
                int p1 = left, p2 = mid + 1;
                int p = 0;
                while (p1 <= mid || p2 <= right) {
                    if (p1 > mid) {
                        sorted[p++] = sum[p2++];
                    } else if (p2 > right) {
                        sorted[p++] = sum[p1++];
                    } else {
                        if (sum[p1] < sum[p2]) {
                            sorted[p++] = sum[p1++];
                        } else {
                            sorted[p++] = sum[p2++];
                        }
                    }
                }
                for (int j = 0; j < sorted.length; j++) {
                    sum[left + j] = sorted[j];
                }
                return ret;
            }
        }
    }


    class Solution_Complex_Thought {
        public int countRangeSum(int[] nums, int lower, int upper) {
            Map<Long, Integer> rangeSumCountMap = new HashMap<>();
            rangeSumCountMap.put(1L * nums[0], 1);
            int sum = nums[0] <= upper && nums[0] >= lower ? 1 : 0;
            for (int i = 1; i < nums.length; i++) {
                Map<Long, Integer> curRangeSumCountMap = new HashMap<>();
                for (long rangeSum : rangeSumCountMap.keySet()) {
                    rangeSum += nums[i];
                    if (rangeSum <= upper && rangeSum >= lower) sum += rangeSumCountMap.getOrDefault(rangeSum, 1);
                    curRangeSumCountMap.put(rangeSum, curRangeSumCountMap.getOrDefault(rangeSum, 0) + 1);
                }

                if (nums[i] <= upper && nums[i] >= lower) sum++;
                curRangeSumCountMap.put(1L * nums[i], curRangeSumCountMap.getOrDefault(nums[i], 0) + 1);
                rangeSumCountMap = curRangeSumCountMap;
            }

            return sum;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[-2,5,-1]");
        System.out.println(solution.countRangeSum(arr, -2, 2));
        System.out.println(solution.countRangeSum(new int[]{0, 0}, 0, 0));
        System.out.println(solution.countRangeSum(new int[]{2147483647, -2147483648, -1, 0}, -1, 0));
    }

    public static void main(String[] args) throws Exception {
        LC327 an = new LC327();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
